package com.coder.algorithm.search;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 广度优先搜索
 *
 * @author yuhushuan
 * @date 2020/10/21 16:07
 */
public class BFS {

    static int[][] visit = new int[10][10];

    static int[][] stepArr = {
            {0, -1},// 上
            {0, 1},// 下
            {-1, 0},// 左
            {1, 0}// 右

    };

    /**
     * 在一个n*n的矩阵里走，从原点（0,0）开始走到终点（n-1,n-1），只能上下左右4个方向走，
     * 只能在给定的矩阵里走，求最短步数。
     * n*n是01矩阵，0代表该格子没有障碍，为1表示有障碍物。
     *
     * @return
     */
    private static int bfs(int[][] mazeArr, int n) {
        Node node = new Node(0, 0, 0);
        Queue<Node> queue = new LinkedList<Node>();
        queue.add(node);
        while (!queue.isEmpty()) {
            Node newNode = queue.poll();
            visit[newNode.x][newNode.y] = 1;
            for (int i = 0; i < 4; i++) {
                int x = newNode.x + stepArr[i][0];
                int y = newNode.y + stepArr[i][1];
                if (x == n - 1 && y == n - 1) {
                    return newNode.step + 1;
                }
                if (x >= 0 && y >= 0 && x < n && y < n
                        && visit[x][y] == 0 && mazeArr[x][y] == 0) {
                    Node next = new Node(x, y, newNode.step + 1);
                    queue.add(next);
                }
            }
        }
        return -1;
    }

    private static class Node {
        private int x;
        private int y;
        private int step;

        public Node(int x, int y, int step) {
            super();
            this.x = x;
            this.y = y;
            this.step = step;
        }
    }
}
